// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

// 求在该柱状图中，能够勾勒出来的矩形的最大面积。
/**
 * @param {number[]} heights
 * @return {number}
 */
// 边界条件考虑不足
var largestRectangleArea = function(heights) {
    let stk = [];
    let max = 0;
    heights.unshift(0);
    heights.push(0);
    for (let i = 0; i < heights.length; i++) {
        console.log(stk, max);
        if (stk.length == 0 || (heights[i] >= stk[stk.length - 1])) {
            stk.push(heights[i]);
        }
        if (heights[i] < stk[stk.length - 1]) {
            let k = 0;
            while (stk[stk.length - 1] > heights[i]) {
                stk.pop();
                k++;
            }
            max = k * heights[i - k] > max ? k * heights[i - k] : max;
        }
    }
    return max;
};

/**
 * @param {number[]} heights
 * @return {number}
 */
const largestRectangleArea = (heights) => {
    let maxArea = 0
    const stack = []
    heights = [0, ...heights, 0]
    for (let i = 0; i < heights.length; i++) { //只有小于才循环，将相等的部分一并入栈
        while (heights[i] < heights[stack[stack.length - 1]]) { // 当前bar比栈顶bar矮
            const stackTopIndex = stack.pop() // 栈顶元素出栈，并保存栈顶bar的索引
            maxArea = Math.max( // 计算面积，并挑战最大面积
                maxArea, // 计算出栈的bar形成的长方形面积
                //这里中间逐次比较，防止出现某几项过高的边界条件
                heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)
            )
        }
        stack.push(i) // 当前bar比栈顶bar高了，入栈
    }
    return maxArea
}